160. 相交链表

Similar Question

leading to the advanced question

Solution Tips

方案一: 哈希表

判断两个链表是否相交，可以使用哈希集合存储链表节点。

首先遍历链表 headA，并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中：

• 如果当前节点不在哈希集合中，则继续遍历下一个节点；
• 如果当前节点在哈希集合中，则后面的节点都在哈希集合中，即从当前节点开始的所有节点都在两个链表的相交部分，因此在链表 headB 中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点，返回该节点。

如果链表 headB 中的所有节点都不在哈希集合中，则两个链表不相交，返回 null。

var getIntersectionNode = function(headA, headB) {
    const visited = new Set();
    let temp = headA;
    while (temp !== null) {
        visited.add(temp);
        temp = temp.next;
    }
    temp = headB;
    while (temp !== null) {
        if (visited.has(temp)) {
            return temp;
        }
        temp = temp.next;
    }
    return null;
}

方案二: 双指针

var getIntersectionNode = function(headA, headB) {
    if (headA === null || headB === null) {
        return null;
    }
    let pA = headA, pB = headB;
    while (pA !== pB) {
        pA = pA === null ? headB : pA.next;
        pB = pB === null ? headA : pB.next;
    }
    return pA;
};

方案三: 脑筋急转弯

先让两个链表剩余长度相同，然后同步遍历，也是空间 O(1)。

class Solution {
public:
    int getLength(ListNode* head) {
        int ans = 0;
        for (;head;head = head->next) ++ans;
        return ans;
    }

    ListNode *getIntersectionNode(ListNode* headA, ListNode* headB) {
        int lenA = getLength(headA);
        int lenB = getLength(headB);
        int len = 0;
        if (lenA > lenB) {
            len = lenB;
            while (lenA-- > lenB)
                headA = headA->next;
        } else {
            len = lenA;
            while (lenB-- > lenA)
                headB = headB->next;
        }
        while (len--) {
            if (headA == headB)
                return headA;
            headA = headA->next;
            headB = headB->next;
        }
        return nullptr;
    }
};